package com.duoduo.剑指Offer;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @program: algorithm
 * @description: 包含min函数的栈02
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.min();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.min();   --> 返回 -2.
 *
 * @author: chaidl  ！
 * @create: 2022-05-21 23:26
 */
public class 包含min函数的栈02 {
	Stack<Integer> inStack;
	Stack<Integer> outStack;
	/** initialize your data structure here. */
	public 包含min函数的栈02() {
		inStack=new Stack<>();
		outStack = new Stack<>();
	}
	
	public void push(int x) {
		inStack.add(x);
		if (outStack.isEmpty() || outStack.peek()>=x){
			outStack.add(x);
		}
	}
	
	public void pop() {
		Integer poll = inStack.pop();
		if (outStack.peek().equals(poll)){
			outStack.pop();
		}
	}
	
	public int top() {
		return inStack.peek();
	}
	
	public int min() {
		return outStack.peek();
	}
}
